class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> res;
        if(n<1) return res;
        res = generateTree(1,n);
        return res;
        
    }
    vector<TreeNode*> generateTree(int start, int end){//start end represent the range of rootval 
        vector<TreeNode*>roots;
        if(start > end) return vector<TreeNode*>{NULL};
        for(int rootval = start; rootval <= end; rootval ++){
            vector<TreeNode*> lefts = generateTree(start, rootval-1);
            vector<TreeNode*> rights = generateTree(rootval+1, end);
            for(int j = 0; j < lefts.size(); j ++){
                for(int k = 0; k < rights.size(); k ++){
                    TreeNode* root = new TreeNode(rootval);
                    root->left = lefts[j];
                    root->right = rights[k];
                    roots.push_back(root);
                }
            }
        }
        return roots;
    }
    
    
};
